//#define _CRT_SECURE_NO_WARNINGS 1
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     struct TreeNode *left;
// *     struct TreeNode *right;
// * };
// */
//
//
// /**
//  * Note: The returned array must be malloced, assume caller calls free().
//  */
//int TreeSize(struct TreeNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    else
//    {
//        return 1 + TreeSize(root->left) + TreeSize(root->right);
//    }
//}
//void _prevOrder(struct TreeNode* root, int* arr, int* i)
//{
//    if (root == NULL)
//    {
//        return;
//    }
//    arr[*i] = root->val;
//    (*i)++;
//    _prevOrder(root->left, arr, i);
//    _prevOrder(root->right, arr, i);
//}
//int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//    int size = TreeSize(root);
//    int* arr = (int*)malloc(sizeof(struct TreeNode) * size);
//    *returnSize = size;
//    int i = 0;
//    _prevOrder(root, arr, &i);
//    return arr;
//}
//
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     struct TreeNode *left;
// *     struct TreeNode *right;
// * };
// */
//
//
// /**
//  * Note: The returned array must be malloced, assume caller calls free().
//  */
//int TreeSize(struct TreeNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    return 1 + TreeSize(root->left) + TreeSize(root->right);
//}
//void _InOrder(struct TreeNode* root, int* arr, int* i)
//{
//    if (root == NULL)
//    {
//        return;
//    }
//    _InOrder(root->left, arr, i);
//    arr[*i] = root->val;
//    (*i)++;
//    _InOrder(root->right, arr, i);
//}
//int* inorderTraversal(struct TreeNode* root, int* returnSize) {
//    int size = TreeSize(root);
//    int* arr = (int*)malloc(sizeof(struct TreeNode) * size);
//    *returnSize = size;
//    int i = 0;
//    _InOrder(root, arr, &i);
//    return arr;
//}
//
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     struct TreeNode *left;
// *     struct TreeNode *right;
// * };
// */
//
//
// /**
//  * Note: The returned array must be malloced, assume caller calls free().
//  */
//int TreeSize(struct TreeNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    else
//    {
//        return 1 + TreeSize(root->left) + TreeSize(root->right);
//    }
//}
//void _PostOrder(struct TreeNode* root, int* arr, int* i)
//{
//    if (root == NULL)
//    {
//        return;
//    }
//    _PostOrder(root->left, arr, i);
//    _PostOrder(root->right, arr, i);
//    arr[*i] = root->val;
//    (*i)++;
//}
//int* postorderTraversal(struct TreeNode* root, int* returnSize) {
//    int size = TreeSize(root);
//    int* arr = (int*)malloc(sizeof(struct TreeNode) * size);
//    *returnSize = size;
//    int i = 0;
//    _PostOrder(root, arr, &i);
//    return arr;
//}
//
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     struct TreeNode *left;
// *     struct TreeNode *right;
// * };
// */
//
//
//int maxDepth(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return 0;
//    }
//    int left_maxDepth = maxDepth(root->left);
//    int right_maxDepth = maxDepth(root->right);
//    return left_maxDepth > right_maxDepth ? left_maxDepth + 1 : right_maxDepth + 1;
//}
//
//
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     struct TreeNode *left;
// *     struct TreeNode *right;
// * };
// */
//int maxDepth(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return 0;
//    }
//    int left_maxDepth = maxDepth(root->left);
//    int right_maxDepth = maxDepth(root->right);
//    return left_maxDepth > right_maxDepth ? left_maxDepth + 1 : right_maxDepth + 1;
//}
//bool isBalanced(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return true;
//    }
//    int leftDepth = maxDepth(root->left);
//    int rightDepth = maxDepth(root->right);
//    return abs(leftDepth - rightDepth) < 2
//        && isBalanced(root->left)
//        && isBalanced(root->right);
//}